package com.zjsru.oneDay;

import java.util.*;

/**
 * 课程表3
 * 使用贪心算法
 *
 *输入：courses = [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
 * 输出：3
 * 解释：
 * 这里一共有 4 门课程，但是你最多可以修 3 门：
 * 首先，修第 1 门课，耗费 100 天，在第 100 天完成，在第 101 天开始下门课。
 * 第二，修第 3 门课，耗费 1000 天，在第 1100 天完成，在第 1101 天开始下门课程。
 * 第三，修第 2 门课，耗时 200 天，在第 1300 天完成。
 * 第 4 门课现在不能修，因为将会在第 3300 天完成它，这已经超出了关闭日期。
 *
 *
 * **/
public class schoolSchedule {
    public int ScheduleCourse(int[][] courses) {
//        排序 建堆
        Arrays.sort(courses, (o1, o2) -> o1[1] - o2[1]);
        PriorityQueue<Integer> pq = new PriorityQueue<>(((o1, o2) -> o2 -o1));
//         遍历课程，加入堆，筛选堆
        int curday  = 0;
        for (int i = 0; i < courses.length; i++) {
            int[] course = courses[i];
            curday += course[0];
            pq.offer(course[0]);
            if(curday > course[1]) curday -= pq.poll();
        }
        return pq.size();
    }
    public static void main(String[] args){
        int[][] courses = new int[][]{
                {100, 200},{200, 1300},{1000, 1250},{2000, 3200}
        };
        schoolSchedule schoolSchedule = new schoolSchedule();
        int result = schoolSchedule.ScheduleCourse(courses);
        System.out.println(result);
    }
}
